class P11417_39643 {

    public static void main(String[] args) {
        int[] a = new int[501];
        a[1] = 0;
        a[2] = 1;
        a[3] = 3;
        a[4] = 7;
        a[5] = 11;
        a[6] = 20;
        a[7] = 26;
        a[8] = 38;
        a[9] = 50;
        a[10] = 67;
        a[11] = 77;
        a[12] = 105;
        a[13] = 117;
        a[14] = 142;
        a[15] = 172;
        a[16] = 204;
        a[17] = 220;
        a[18] = 265;
        a[19] = 283;
        a[20] = 335;
        a[21] = 379;
        a[22] = 420;
        a[23] = 442;
        a[24] = 518;
        a[25] = 558;
        a[26] = 607;
        a[27] = 661;
        a[28] = 737;
        a[29] = 765;
        a[30] = 870;
        a[31] = 900;
        a[32] = 980;
        a[33] = 1052;
        a[34] = 1117;
        a[35] = 1199;
        a[36] = 1331;
        a[37] = 1367;
        a[38] = 1440;
        a[39] = 1526;
        a[40] = 1666;
        a[41] = 1706;
        a[42] = 1859;
        a[43] = 1901;
        a[44] = 2025;
        a[45] = 2169;
        a[46] = 2258;
        a[47] = 2304;
        a[48] = 2496;
        a[49] = 2580;
        a[50] = 2725;
        a[51] = 2839;
        a[52] = 2987;
        a[53] = 3039;
        a[54] = 3228;
        a[55] = 3362;
        a[56] = 3566;
        a[57] = 3694;
        a[58] = 3807;
        a[59] = 3865;
        a[60] = 4165;
        a[61] = 4225;
        a[62] = 4346;
        a[63] = 4556;
        a[64] = 4748;
        a[65] = 4908;
        a[66] = 5157;
        a[67] = 5223;
        a[68] = 5419;
        a[69] = 5575;
        a[70] = 5856;
        a[71] = 5926;
        a[72] = 6274;
        a[73] = 6346;
        a[74] = 6491;
        a[75] = 6741;
        a[76] = 6961;
        a[77] = 7157;
        a[78] = 7454;
        a[79] = 7532;
        a[80] = 7884;
        a[81] = 8100;
        a[82] = 8261;
        a[83] = 8343;
        a[84] = 8779;
        a[85] = 8991;
        a[86] = 9160;
        a[87] = 9358;
        a[88] = 9690;
        a[89] = 9778;
        a[90] = 10255;
        a[91] = 10489;
        a[92] = 10757;
        a[93] = 10969;
        a[94] = 11154;
        a[95] = 11392;
        a[96] = 11856;
        a[97] = 11952;
        a[98] = 12253;
        a[99] = 12595;
        a[100] = 13015;
        a[101] = 13115;
        a[102] = 13508;
        a[103] = 13610;
        a[104] = 14006;
        a[105] = 14486;
        a[106] = 14695;
        a[107] = 14801;
        a[108] = 15341;
        a[109] = 15449;
        a[110] = 15906;
        a[111] = 16160;
        a[112] = 16672;
        a[113] = 16784;
        a[114] = 17225;
        a[115] = 17515;
        a[116] = 17855;
        a[117] = 18263;
        a[118] = 18496;
        a[119] = 18806;
        a[120] = 19586;
        a[121] = 19806;
        a[122] = 20047;
        a[123] = 20329;
        a[124] = 20693;
        a[125] = 20993;
        a[126] = 21686;
        a[127] = 21812;
        a[128] = 22260;
        a[129] = 22556;
        a[130] = 23101;
        a[131] = 23231;
        a[132] = 23939;
        a[133] = 24287;
        a[134] = 24552;
        a[135] = 25146;
        a[136] = 25670;
        a[137] = 25806;
        a[138] = 26343;
        a[139] = 26481;
        a[140] = 27277;
        a[141] = 27601;
        a[142] = 27882;
        a[143] = 28264;
        a[144] = 29128;
        a[145] = 29496;
        a[146] = 29785;
        a[147] = 30303;
        a[148] = 30739;
        a[149] = 30887;
        a[150] = 31712;
        a[151] = 31862;
        a[152] = 32450;
        a[153] = 32990;
        a[154] = 33655;
        a[155] = 34049;
        a[156] = 34893;
        a[157] = 35049;
        a[158] = 35362;
        a[159] = 35728;
        a[160] = 36576;
        a[161] = 37000;
        a[162] = 37729;
        a[163] = 37891;
        a[164] = 38375;
        a[165] = 39155;
        a[166] = 39484;
        a[167] = 39650;
        a[168] = 40782;
        a[169] = 41094;
        a[170] = 41815;
        a[171] = 42421;
        a[172] = 42929;
        a[173] = 43101;
        a[174] = 43782;
        a[175] = 44452;
        a[176] = 45284;
        a[177] = 45692;
        a[178] = 46045;
        a[179] = 46223;
        a[180] = 47555;
        a[181] = 47735;
        a[182] = 48528;
        a[183] = 48950;
        a[184] = 49666;
        a[185] = 50138;
        a[186] = 50867;
        a[187] = 51373;
        a[188] = 51929;
        a[189] = 52793;
        a[190] = 53602;
        a[191] = 53792;
        a[192] = 54880;
        a[193] = 55072;
        a[194] = 55457;
        a[195] = 56387;
        a[196] = 57255;
        a[197] = 57451;
        a[198] = 58576;
        a[199] = 58774;
        a[200] = 59874;
        a[201] = 60338;
        a[202] = 60739;
        a[203] = 61277;
        a[204] = 62393;
        a[205] = 62917;
        a[206] = 63326;
        a[207] = 64064;
        a[208] = 65056;
        a[209] = 65624;
        a[210] = 67169;
        a[211] = 67379;
        a[212] = 68007;
        a[213] = 68499;
        a[214] = 68924;
        a[215] = 69474;
        a[216] = 70878;
        a[217] = 71454;
        a[218] = 71887;
        a[219] = 72393;
        a[220] = 73685;
        a[221] = 74289;
        a[222] = 75162;
        a[223] = 75384;
        a[224] = 76616;
        a[225] = 77756;
        a[226] = 78205;
        a[227] = 78431;
        a[228] = 79683;
        a[229] = 79911;
        a[230] = 80896;
        a[231] = 82030;
        a[232] = 82938;
        a[233] = 83170;
        a[234] = 84511;
        a[235] = 85113;
        a[236] = 85813;
        a[237] = 86361;
        a[238] = 87410;
        a[239] = 87648;
        a[240] = 89568;
        a[241] = 89808;
        a[242] = 90589;
        a[243] = 91399;
        a[244] = 92123;
        a[245] = 93075;
        a[246] = 94044;
        a[247] = 94722;
        a[248] = 95694;
        a[249] = 96270;
        a[250] = 97295;
        a[251] = 97545;
        a[252] = 99477;
        a[253] = 100169;
        a[254] = 100674;
        a[255] = 101904;
        a[256] = 102928;
        a[257] = 103184;
        a[258] = 104201;
        a[259] = 104891;
        a[260] = 106431;
        a[261] = 107367;
        a[262] = 107888;
        a[263] = 108150;
        a[264] = 109986;
        a[265] = 110666;
        a[266] = 111843;
        a[267] = 112461;
        a[268] = 113257;
        a[269] = 113525;
        a[270] = 115442;
        a[271] = 115712;
        a[272] = 117024;
        a[273] = 118376;
        a[274] = 118921;
        a[275] = 120011;
        a[276] = 121535;
        a[277] = 121811;
        a[278] = 122364;
        a[279] = 123366;
        a[280] = 125426;
        a[281] = 125706;
        a[282] = 126819;
        a[283] = 127101;
        a[284] = 127945;
        a[285] = 129325;
        a[286] = 130614;
        a[287] = 131380;
        a[288] = 133444;
        a[289] = 133988;
        a[290] = 135237;
        a[291] = 135911;
        a[292] = 136779;
        a[293] = 137071;
        a[294] = 138772;
        a[295] = 139530;
        a[296] = 140694;
        a[297] = 142098;
        a[298] = 142691;
        a[299] = 143517;
        a[300] = 145817;
        a[301] = 146621;
        a[302] = 147222;
        a[303] = 147924;
        a[304] = 149396;
        a[305] = 150180;
        a[306] = 151953;
        a[307] = 152259;
        a[308] = 154135;
        a[309] = 154851;
        a[310] = 156188;
        a[311] = 156498;
        a[312] = 158686;
        a[313] = 158998;
        a[314] = 159623;
        a[315] = 161765;
        a[316] = 162705;
        a[317] = 163021;
        a[318] = 164278;
        a[319] = 165156;
        a[320] = 167140;
        a[321] = 167884;
        a[322] = 169317;
        a[323] = 170215;
        a[324] = 172267;
        a[325] = 173567;
        a[326] = 174216;
        a[327] = 174974;
        a[328] = 176266;
        a[329] = 177146;
        a[330] = 179651;
        a[331] = 179981;
        a[332] = 180969;
        a[333] = 182169;
        a[334] = 182834;
        a[335] = 183696;
        a[336] = 186480;
        a[337] = 186816;
        a[338] = 187921;
        a[339] = 188707;
        a[340] = 190743;
        a[341] = 191683;
        a[342] = 193672;
        a[343] = 194554;
        a[344] = 195910;
        a[345] = 197590;
        a[346] = 198279;
        a[347] = 198625;
        a[348] = 200557;
        a[349] = 200905;
        a[350] = 203090;
        a[351] = 204764;
        a[352] = 206764;
        a[353] = 207116;
        a[354] = 208517;
        a[355] = 209431;
        a[356] = 210491;
        a[357] = 212279;
        a[358] = 212992;
        a[359] = 213350;
        a[360] = 216770;
        a[361] = 217454;
        a[362] = 218175;
        a[363] = 219517;
        a[364] = 221753;
        a[365] = 222693;
        a[366] = 224142;
        a[367] = 224508;
        a[368] = 226300;
        a[369] = 227632;
        a[370] = 229233;
        a[371] = 230227;
        a[372] = 232295;
        a[373] = 232667;
        a[374] = 234372;
        a[375] = 236122;
        a[376] = 237606;
        a[377] = 238654;
        a[378] = 241435;
        a[379] = 241813;
        a[380] = 244097;
        a[381] = 244981;
        a[382] = 245742;
        a[383] = 246124;
        a[384] = 248620;
        a[385] = 250692;
        a[386] = 251461;
        a[387] = 252859;
        a[388] = 254015;
        a[389] = 254403;
        a[390] = 257388;
        a[391] = 258482;
        a[392] = 260750;
        a[393] = 261662;
        a[394] = 262447;
        a[395] = 263465;
        a[396] = 266597;
        a[397] = 266993;
        a[398] = 267786;
        a[399] = 269792;
        a[400] = 272512;
        a[401] = 272912;
        a[402] = 274505;
        a[403] = 275627;
        a[404] = 276831;
        a[405] = 279099;
        a[406] = 280916;
        a[407] = 282042;
        a[408] = 284934;
        a[409] = 285342;
        a[410] = 287119;
        a[411] = 288073;
        a[412] = 289301;
        a[413] = 290409;
        a[414] = 292830;
        a[415] = 293900;
        a[416] = 296284;
        a[417] = 297252;
        a[418] = 299165;
        a[419] = 299583;
        a[420] = 303843;
        a[421] = 304263;
        a[422] = 305104;
        a[423] = 306634;
        a[424] = 308310;
        a[425] = 310030;
        a[426] = 311719;
        a[427] = 312865;
        a[428] = 314141;
        a[429] = 316337;
        a[430] = 318202;
        a[431] = 318632;
        a[432] = 322088;
        a[433] = 322520;
        a[434] = 324465;
        a[435] = 326595;
        a[436] = 327895;
        a[437] = 329123;
        a[438] = 330860;
        a[439] = 331298;
        a[440] = 334638;
        a[441] = 336990;
        a[442] = 339023;
        a[443] = 339465;
        a[444] = 341941;
        a[445] = 343089;
        a[446] = 343978;
        a[447] = 345016;
        a[448] = 347896;
        a[449] = 348344;
        a[450] = 351989;
        a[451] = 353239;
        a[452] = 354587;
        a[453] = 355639;
        a[454] = 356544;
        a[455] = 359014;
        a[456] = 362258;
        a[457] = 362714;
        a[458] = 363627;
        a[459] = 365841;
        a[460] = 368621;
        a[461] = 369081;
        a[462] = 372714;
        a[463] = 373176;
        a[464] = 375448;
        a[465] = 377728;
        a[466] = 378657;
        a[467] = 379123;
        a[468] = 382855;
        a[469] = 384115;
        a[470] = 386156;
        a[471] = 387250;
        a[472] = 389118;
        a[473] = 390430;
        a[474] = 392311;
        a[475] = 394241;
        a[476] = 397197;
        a[477] = 398925;
        a[478] = 399878;
        a[479] = 400356;
        a[480] = 404916;
        a[481] = 406260;
        a[482] = 407221;
        a[483] = 409663;
        a[484] = 411907;
        a[485] = 413159;
        a[486] = 415832;
        a[487] = 416318;
        a[488] = 418250;
        a[489] = 419386;
        a[490] = 422487;
        a[491] = 422977;
        a[492] = 425725;
        a[493] = 427113;
        a[494] = 429394;
        a[495] = 432868;
        a[496] = 435300;
        a[497] = 436636;
        a[498] = 438613;
        a[499] = 439111;
        a[500] = 442011;
       
        while (true) {
            int i = Integer.parseInt(readLn());
           
            if (i == 0) break;
           
            System.out.println(a[i]);
           
        }
    }
   
    public static void mainPrecalc(String[] args) {

        for (int N = 1; N < 501; N++) {
            int g = 0;

            for (int i = 1; i < N; i++)
                for (int j = i + 1; j <= N; j++)
                {
                    g += GCD(i, j);
                }
           
            System.out.println("a[" + N + "] = " + g + ";");
           
        }

    }
   

    public static int GCD(int a, int b) {
        if (b == 0)
            return a;
        return GCD(b, a % b);
    }
   
    static String readLn() {
        String newLine = System.getProperty("line.separator");
        StringBuilder buffer = new StringBuilder();
        int car = -1;
        try {
            car = System.in.read();
            while ((car > 0) && (car != newLine.charAt(0))) {
                buffer.append((char) car);
                car = System.in.read();
            }
            if (car == newLine.charAt(0))
                System.in.skip(newLine.length() - 1);
        } catch (java.io.IOException e) {
            return (null);
        }
        if ((car < 0) && (buffer.length() == 0))
            return (null);
        return (buffer.toString()).trim();
    }
   
   
}